package foundation.two_n_queen;

import java.util.Scanner;

/**
 * 2n皇后问题
 * 给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。
 * 现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，
 * 任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
 */
public class Main {
    static int n = 0;
    static int res = 0; // 记录结果
    static int black = 2, write = 3;
    static int[][] board; // 放置棋子
    static int[] tmpBoardBlack, tmpBoardWrite;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        tmpBoardBlack = new int[n]; // 表示该行棋子放置的列
        tmpBoardWrite = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        setBlack(0);
        System.out.println(res);
    }

    /**
     * 判断该位置是否能放置某棋子
     * @param row
     * @return
     */
    public static boolean isLegalToBlack(int row) {
        for (int i = 0; i < row; i++) {
            if (tmpBoardBlack[i] == tmpBoardBlack[row] || Math.abs(i - row) == Math.abs(tmpBoardBlack[i] - tmpBoardBlack[row])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 放置黑色棋子
     * @param row 当前的行
     */
    public static void setBlack(int row) {
        // 终止条件
        if (row == n) {
            // 所有黑色棋子摆放完毕，开始摆放白色棋子
            setWrite(0);
        } else {
            // 单层搜索逻辑
            for (int i = 0; i < n; i++) {
                if (board[row][i] == 1) {
                    tmpBoardBlack[row] = i;
                    if (isLegalToBlack(row)) {
                        board[row][i] = black;
                        setBlack(row + 1);
                    }
                    board[row][i] = 1;
                }
            }
        }
    }

    /**
     * 判断白色棋子放置是否合法
     * @param row
     * @return
     */
    public static boolean isLegalToWrite(int row) {
        for (int i = 0; i < row; i++) {
            if (tmpBoardWrite[i] == tmpBoardWrite[row] || Math.abs(i - row) == Math.abs(tmpBoardWrite[i] - tmpBoardWrite[row])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 放置白色棋子
     * @param row
     */
    public static void setWrite(int row) {
        if (row == n) {
            res ++;
        } else {
            for (int i = 0; i < n; i++) {
                if (board[row][i] == 1) {
                    tmpBoardWrite[row] = i;
                    if (isLegalToWrite(row)) {
                        setWrite(row + 1);
                    }
                }
            }
        }
    }
}
